package swardToOffer.struct_3_linkedlist;

import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class CopyComplexList {

    public Node copyRandomList2(Node head) {
        if (head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        // 4. 构建新链表的 next 和 random 指向
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }

    public Node copyRandomList(Node head) {
        //1. 复制原始链表的任意节点N并创建新节点N'链接到N的后面
        cloneNodes(head);
        //2. 原始链表中节点N的random指向S,则添加的新节点N'指向S.next
        connectRandom(head);
        //3. 丢弃原始链表的节点（奇数）
        return reConnectNodes(head);
    }

    private Node reConnectNodes(Node head) {
        Node p = head;
        Node clonedHead = null;
        Node p_ = null;
        if (p != null) {
            clonedHead = p_ = p.next;
            p.next = p_.next;
            p = p.next;
        }
        while (p != null) {
            p_.next = p.next;
            p_ = p_.next;
            p.next = p_.next;
            p = p.next;
        }
        return clonedHead;
    }

    private void connectRandom(Node head) {
        Node p = head;
        while (p != null) {
            Node p_ = p.next;
            if (p.random != null) p_.random = p.random.next;
            p = p_.next;
        }
    }

    private void cloneNodes(Node head) {
        Node p = head;
        while (p != null) {
            Node p_ = new Node(p.val);
            p_.val = p.val;
            p_.next = p.next;
            p_.random = null;
            p.next = p_;
            p = p_.next;
        }
    }


    public static void main(String[] args) {
        CopyComplexList Main = new CopyComplexList();
        Node head = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        head.next = node1;
        node1.next = node2;
        head.random = node2;
        Main.cloneNodes(head);
        Main.connectRandom(head);
//        while (head!= null) {
//            System.out.print(head.val + "\t");
//            head = head.next;
//        }
        Node cloneHead = Main.reConnectNodes(head);
        while (cloneHead != null) {
            System.out.print(cloneHead.val + "\t");
            cloneHead = cloneHead.next;
        }
    }
}
